package main

func possibleBipartition(n int, dislikes [][]int) bool {
	adj := make([][]int, n+1)
	for _, dislike := range dislikes {
		adj[dislike[0]] = append(adj[dislike[0]], dislike[1])
		adj[dislike[1]] = append(adj[dislike[1]], dislike[0])
	}
	colors := make([]int, n+1)
	for i := 1; i <= n; i++ {
		if colors[i] == 0 && !dfs(adj, i, 1, colors) {
			return false
		}
	}

	return true
}

func dfs(adj [][]int, node int, color int, colors []int) bool {
	if colors[node] != 0 {
		return colors[node] == color
	}
	colors[node] = color
	for _, next := range adj[node] {
		if !dfs(adj, next, -color, colors) {
			return false
		}
	}

	return true
}
